package pro.softzhang.algo.lc400;

import pro.softzhang.algo.common.Node;
import pro.softzhang.algo.common.Utils;

/**
 * TODO 加练
 */
public class LC430_FlattenAMultilevelDoublyLinkedList {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node1.next = node2;
        node2.prev = node1;
        node2.next = node3;
        node3.prev = node2;
        node2.child = node5;
        node5.next = node6;
        node6.prev = node5;
        Node head = new LC430_FlattenAMultilevelDoublyLinkedList().flatten(node1);
        Utils.printDoublyLinkedList(head);
    }

    public Node flatten(Node head) {
        doFlatten(head);
        return head;
    }

    public Node doFlatten(Node head) {
        Node node = head, tail = null;
        while (node != null) {
            Node next = node.next;
            if(node.child != null) {
                Node child = node.child;
                // 获取子链表尾结点
                Node childTail = doFlatten(node.child);
                node.child = null;
                // Node的后序设置为child
                node.next = child;
                child.prev = node;
                childTail.next = next;
                if(next != null) {
                    next.prev = childTail;
                }
                tail = childTail;
            } else {
                tail = node;
            }
            node = next;
        }
        return tail;
    }
}
